#pragma once
#include<iostream>
#include<vector>
#include"MemUtil.h"
using namespace std;



//用于不同范围的值访问不同对象
template<class T>   //T为指针
class RangeEle{
private:
    //存储范围左区间
    vector<uint64_t> rangeLeftVec;

    vector<T> eleVec;

    void init(const vector<T>& eleVec, const vector<uint64_t>& rangeLeftVec){
        this->rangeLeftVec = rangeLeftVec;
        this->eleVec = eleVec;
    }

    vector<uint64_t> getAvgRangeLeft(const int& count){
        vector<uint64_t> rangeLeft;
        const uint64_t rangeLen = UINT64_MAX / count + (UINT64_MAX % count == 0 ? 0 : 1);
        int i = 0;
        for(uint64_t tmpLeft = 0; i < count; tmpLeft += rangeLen, i++){ //以tmpLeft判断容易溢出
            rangeLeft.push_back(tmpLeft);
        }
        return rangeLeft;
    }

    int binarySearchIndex(const uint64_t& val, const bool& getInsertLoc){
        int left = 0, right = rangeLeftVec.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;        //防止溢出
            const uint64_t& midVal = rangeLeftVec[mid];
            if(midVal == val){
                if(getInsertLoc){
                    throw string("An attempt was made to add an existing left section");
                }
                return mid;
            }
            else if(midVal < val){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        return getInsertLoc ? left : right;  //在这个时候 已经right在左 left在右了
    }



public:

    RangeEle(const vector<T>& eleVec, const vector<uint64_t>& rangeLeftVec){
        if(eleVec.size() != rangeLeftVec.size())
            throw string("diff size");
        init(eleVec, rangeLeftVec);
    }

    RangeEle(const vector<T>& eleVec, const int& eleCount){
        if(eleVec.size() != eleCount)
            throw string("diff size");
        init(eleVec, getAvgRangeLeft(eleCount));
    }

    ~RangeEle(){
        MemUtil::clearVecMem(eleVec);
    }

    T getProbEle(const uint64_t& val){
        return eleVec[binarySearchIndex(val, false)];
    }

    void addEle(const uint64_t& rangeLeft, const T& ele){
        int insertLoc = binarySearchIndex(rangeLeft, true);
        rangeLeftVec.insert(rangeLeftVec.begin() + insertLoc, rangeLeft);
        eleVec.insert(eleVec.begin() + insertLoc, ele);
    }
};
